package com.lsa.iview.unsorted;

import java.util.List;

public class CountChange {
	public static int countChange(int money, List<Integer> nominations) {
		if (money == 0) {
			return 0;
		}
		return countChangeFunct(0, money, nominations);
	}
	
	private static int countChange(int no, int money, List<Integer> nominations) {
		if (money == 0) {
			return no + 1;
		}
		else if (nominations.isEmpty()) {
			return no;
		}
		
		int firstSum = 0;
		while(firstSum <= money) {
			no = countChange(no, money - firstSum, tail(nominations));
			firstSum += head(nominations);
		}
		
		return no;
	}
	
	/**
	 * Functional variant of the countChange
	 * @param noOfWays - summator of number of ways to count change
	 * @param money - input ammount of money to change
	 * @param nominations -  list of possible nominations to use
	 * @return
	 */
	private static int countChangeFunct(int noOfWays, int money, List<Integer> nominations) {
		if (money == 0) {
			return noOfWays + 1;
		}
		else if (nominations.isEmpty()) {
			return noOfWays;
		}
		
		return countChangeUseHead(noOfWays, money, 0, nominations);
	}
	
	private static int countChangeUseHead(int noOfWays, int money, int headSum, List<Integer> nominations) {
		if (headSum == money) {
			return noOfWays + 1;
		}
		else if (headSum > money) {
			return noOfWays;
		}
		//PRE : headSum < money
		return countChangeFunct(
				countChangeUseHead(noOfWays, money, headSum + head(nominations), nominations), 
				money - headSum, tail(nominations));
	}
	
	private static int head(List<Integer> l) {
		return l.get(0);
	}
	
	private static List<Integer> tail(List<Integer> l) {
		return l.subList(1, l.size());
	}
}
